20210114第七章复习

第 7 章 二元关系

有序对与笛卡尔积

由两个元素按照一定顺序排列成的二元组称为一个有序对或序偶，记作<x,y>，x 是他的第一个元素，y 是他的第二个元素。<x,y>不等于<y,x>

A,B 为集合，用 A 中元素为第一元素，B 中元素为第二元素构成有序对，所有这样的有序对组成的集合称作 A 和 B 的笛卡尔积，记作 AXB
|A|=m,|B|=n,则|AXB|=mn

笛卡尔积不满足交换率和结合律，但满足分配律。
AX（BUC）=（AXB）U（BXC）

二元关系

集合非空，且他的元素都是有序对，或集合是空集，则称该集合为一个二元关系。二元关系也可简称关系。对于二元关系 R，<x,y>属于 R，记作 xRy，不属于则记作 xR\y
AXB 的任何子集定义的二元关系称作从 A 到 B 的二元关系，特别当 A=B 时称作 A 上的二元关系。

|A|=n，则|AXA|=n^2，AXA 的子集有 2^n^2 个，每个子集都是不同的二元关系。

空集称作 A 上的空关系
A 上的全域关系：E_A = {<x,y>|x 属于 A 合取 y 属于 A} = AXA
A 上的恒等关系：I_A = {<x,x>|x 属于 A}
A 上的小于等于关系： L_A，前项小于等于后项
A 上的整除关系： D_A，前项整除后项
A 上的包含关系： R_ 包含于，就是二元关系里的前项包含于后项

给出一个关系的方法：集合表达式/关系矩阵/关系图
关系矩阵：M_R
r_ij= 1(若 x_i R x_j)
r_ij=0(若 x_i R 杠 x_j)
关系图：G_R
A={x_1,x_2…x_n}，则 G_R 有 n 个顶点，叫 x_1 到 x_n。如果<x_i,x_j>属于 R，则 G_R 中有一条 x_i 到 x_j 的有向边。

关系的运算

基本运算有七种
1.R 中所有有序对的第一元素构成的集合称作 R 的定义域，记作 domR。
2.R 中所有有序对的第二元素构成的集合称作 R 的值域，记作 ranR
3.R 的定义域和值域的并集称作 R 的域，记作 fldR，fldR=domRUranR
4.R 为二元关系，R 的逆关系简称 R 的逆，记作 R^-1，就是所有有序对前后颠倒
5.G 对 F 的右复合，记作 F 圈 G，F 圈 G={<x,y>|存在 t(<x,t>属于 F 合取<t,y>属于 G)}。就是两个关系，如果第一个关系有<x,t>，第二个关系有<t,y>，那么第一个关系圈第二个关系就有<x,y>
6.R 为二元关系，A 是集合，R 在 A 上的限制记作 R 上箭头少左一撇 A。R 上箭头少左一撇 A={<x,y>|xRy 合取 x 属于 A}。就是限制一下 R，R 中有序对的第一个必须在 A 中出现。
7.R 为二元关系，A 是集合，A 在 R 下的像记作 R[A]，R[A]=ran(R 上箭头少左一撇 A)
8.R 为 A 上的关系，n 为自然数，则 R 的 n 次幂 R^n 定义为：R^0={<x,x>|x 属于 A|=I_A ,R^n+1=R^n 圆圈 R（用矩阵计算 n 次幂的时候注意是逻辑加，1+1=1，只有 0+0=0）
（F 圆圈 G) 圆圈 H=F 圆圈（G 圆圈 H）
（F 圆圈 G）^-1=G^-1 圆圈 F^-1
R 圆圈 I_A=I_A 圆圈 R=R

设 A 为 n 元集，R 是 A 上的关系，则存在自然数 s 和 t，使得 R^s=R^t。很明显无论乘多少次方，他总是 AXA 的一个子集，|AXA|=n^2, |P(AXA)|=2^n^2 因此总有重复的时候。

关系的性质

5 种：
自反性、反自反性、对称性、反对称性、传递性。
自反：任取 x（x 属于 A -> <x,x>属于 R），则称 R 在 A 上是自反的（I_A、L_A）
反自反：任取 x（x 属于 A -> <x,x>不属于 R），则称 R 在 A 上是反自反的（空关系）
对称：若 任取 x 任取 y（x，y 属于 A 合取<x,y>属于 R --> <y,x>属于 R），则称 R 为 A 上对称的关系（I_A、空关系、全域关系 E_A）
反对称：若 任取 x 任取 y（x，y 属于 A 合取<x,y>属于 R 合取<y,x>属于 R --> x=y）（I_A、空关系、A 只有一个元素或没有元素 的时候 E_A）
传递：任取 x 任取 y 任取 z（x，y，z 属于 A 合取<x,y>属于 R 合取<y,z>属于 R ---> <x,z>属于 R），则称 R 为 A 上的传递关系。
定理：
1.R 自反当且仅当 I_A 属于 R
2.R 反自反当且仅当 R 交 I_A=空集
3.R 在 A 上对称当且仅当 R=R^-1
4.R 在 A 上反对称当且仅当 R 交 R^-1 包含于 I_A
5.R 在 A 上传递当且仅当 R 圆圈 R 包含于 R


关系的闭包

自反闭包 r(R)
对称闭包 s(R)
传递闭包 t(R)
都是在不满足自反/对称/传递的二元关系 R 中，尽量添加最少的有序对达成新的二元关系 R‘，使 R' 具有自反性/对称性/传递性。
设 R 为 A 上的关系
(1)r(R)=RUR^0
(2)s(R)=RUR^-1
(3)t(R)=RUR^2UR^3U…

等价关系与划分

若 R 是非空集合上的关系，且是自反的、对称的、传递的，则称 R 是 A 上的等价关系。
R 是一个等价关系，若<x,y>属于 R，则 x 等价于 y，记作 x~y（就是 x，y 相等）
设 R 为非空集合 A 上的等价关系，任取 x 属于 A，令[x]_R={y|y 属于 A 合取 xRy}，称[x]_R 为 x 关于 R 的等价类，简称为 x 的等价类，[x] 或 x 上划线。（[x]_R 就是关系下所有与 x 相等的元素的集合）

R 是非空集合 A 上的等价关系，定理：
1）任取 x 属于 A，[x] 是 A 的非空子集
2）任取 x，y 属于 A，如果 xRy，则[x]=[y]
3）任取 x，y 属于 A，如果 xR\y，则[x] 与[y] 不交
4）U{[x]|x 属于 A}=A

R 为非空集合 A 上的等价关系，以 R 的所有等价类作为元素的集合称为 A 关于 R 的商集，记作 A/R。（就是等价类把集合划分为一坨一坨的，所有坨组成的集合就是商集）

设 A 为非空集合，若 A 的子集族 pi（pi 包含于 P(A)，是 A 的子集构成的集合）满足下面的条件：
（1）空集不属于 PI
（2）任取 x 任取 y（x，y 属于 PI 合取 x 不等于 y-->x 交 y=空集）
（3）UPI=A
则称 PI 是 A 的一个划分，PI 中的元素为 A 的划分块。
（就是把 A 中的元素分块，块间不重复，没有空块，就把块的集合称为划分）

偏序关系

R 是非空集合 A 上的关系，如果 R 是自反的、反对称的和 传递的，则称 R 为 A 上的偏序关系，记作小于等于（直线向中间收拢变曲），读作 x 小于等于 y，表示 x 在 y 的前面。（就是<x,y>存在而<y,x>不存在）
x<y（直线向中间收拢变曲），等价于 x 小于等于 y 且 x 不等于 y（就是不能是<x,x>）
x 与 y 可比，等价于 x 小于等于 y 析取 y 小于等于 x（就是要么有<x,y>要么有<y,x>）

R 为非空集合 A 上的偏序关系，如果任取 x，y 属于 A，x 与 y 都是可比的，则称 R 为 A 上的全序关系（或线序关系）
集合 A 和 A 上的偏序关系一起称作偏序集，记作<A,小于等于>

设<A,小于等于>为偏序集，任取 x，y 属于 A，如果 x<y 且不存在 z 属于 A 使得 x<z<y，则称 y 覆盖 x。（就是 x 他只能出发去 y，别无它路。那 y 就覆盖 x）

哈斯图

设<A,小于等于>为偏序集，B 包含于 A，y 属于 B
（1）若任取 x（x 属于 B-->y 小于等于 x）成立，则称 y 为 B 的最小元。（就是 x 得能到偏序关系所有点）
（2）若任取 x（x 属于 B-->x 小于等于 y）成立，则称 y 为 B 的最大元。（就是偏序关系的集合所有点都能到 y）
（3）若任取 x（x 属于 B 合取 x 小于等于 y-->x=y）成立，则称 y 为 B 的极小元。（就是没有人小于 y，只有他自己等于自己）
（4）若任取 x（x 属于 B 合取 y 小于等于 x-->x=y）成立，则称 y 为 B 的极大元。（就是没有人大于 y，只有他自己等于自己）

设<A,小于等于>为偏序集，B 包含于 A，y 属于 A。
（1）若任取 x（x 属于 B-->x 小于等于 y）成立，则称 y 为 B 的上界。（从 A 里选一个集合 B，所有人小于等于 y（y 在 A 里就行），y 是 B 上界）
（2）若任取 x（x 属于 B-->y 小于等于 x）成立，则称 y 为 B 的下界。（从 A 里选一个集合 B，y 小于等于所有人（y 在 A 里就行），y 是 B 下界）
（3）令 C={y|y 为 B 的上界}，则称 C 的最小元为 B 的最小上界或上确界。（上界中最小的，B 的最大元一定是最小上界）
（4）令 D={y|y 为 B 的下界}，则称 D 的最大元为 B 的最大下界或下确界。（下界中最大的，B 的最小元一定是最大上界）